package class08;

import java.util.ArrayList;

public class Code03_PrintAllPermutations {


	public static ArrayList<String> Permutation(String str) {
		ArrayList<String> res = new ArrayList<>();
		if (str == null || str.length() == 0) {
			return res;
		}
		char[] chs = str.toCharArray();
		process(chs, 0, res);
		res.sort(null);
		return res;
	}


	/**
	 * 省空间做法
	 *
	 * 用到了回溯 + 分支限界法
	 * @param chs
	 * @param i
	 * @param res
	 */

	// i往后（即chs[i...length-1]范围上）的所有的字符，都可以被放在i位置上。 i的后序都做同样的尝试
	// chs[0...i-1]范围上的，是之前做的选择
	// 请把所有字符串形成的全排列的所有结果放到res中
	public static void process(char[] chs, int i, ArrayList<String> res) {
		if (i == chs.length) {
			res.add(String.valueOf(chs));
		}
//		boolean[] visit = new boolean[26]; // 表示某个字符是否已经试过的一张表
		for (int j = i; j < chs.length; j++) {

			/**
			 *  if语句用于控制是否进行去重的全排列。 加上 -> 去重
			 *  
			 *  分支限界法：if的过程就属于剪枝，减去不可能的分枝
			 *
			 *  可以不利用if语句，跑完全部的结果后，在对res做去重操作。两种方法在复杂度上一样，但是剪枝的方法常数项时间更小，因此会更快
			 */
//			if (!visit[chs[j] - 'a']) {
//				visit[chs[j] - 'a'] = true;

				// i往后（即chs[i...length-1]范围上）的所有的字符，都可以被放在i位置上。 i的后序都做同样的尝试
				swap(chs, i, j);
				process(chs, i + 1, res);
				//第二个swap就是回溯。回溯=子递归调用完成后把环境恢复调用前状态
				swap(chs, i, j); // 后序走完之后，交换回来，恢复到原来的样子

//			}
		}
	}

	public static void swap(char[] chs, int i, int j) {
		char tmp = chs[i];
		chs[i] = chs[j];
		chs[j] = tmp;
	}


	public static void main(String[] args) {
		ArrayList<String> res = Permutation("abc");
		for (String str : res) {
			System.out.println(str);
		}

	}

}
